Primal sparse Max-margin Markov networks
Jun Zhu
Eric P. Xing
Bo Zhang
Max-margin Markov networks (M<sup>3</sup>N) have shown great promise in structured prediction and relational learning. Due to the KKT conditions, the M<sup>3</sup>N enjoys dual sparsity. However, the existing M<sup>3</sup>N formulation does not enjoy primal sparsity, which is a desirable property for selecting significant features and reducing the risk of over-fitting. In this paper, we present an <i>l</i><sub>1</sub>-norm regularized max-margin Markov network (<i>l</i><sub>1</sub>-M<sup>3</sup>N), which enjoys dual and primal sparsity simultaneously. To learn an <i>l</i><sub>1</sub>-M<sup>3</sup>N, we present three methods including projected sub-gradient, cutting-plane, and a novel EM-style algorithm, which is based on an equivalence between <i>l</i><sub>1</sub>-M<sup>3</sup>N and an adaptive M<sup>3</sup>N. We perform extensive empirical studies on both synthetic and real data sets. Our experimental results show that: (1) <i>l</i><sub>1</sub>-M<sup>3</sup>N can effectively select significant features; (2) <i>l</i><sub>1</sub>-M<sup>3</sup>N can perform as well as the pseudo-primal sparse Laplace M<sup>3</sup>N in prediction accuracy, while consistently outperforms other competing methods that enjoy either primal or dual sparsity; and (3) the EM-algorithm is more robust than the other two in pre-diction accuracy and time efficiency.
